package searchtree;

import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Test2 {
    /**
     * 只出现一次的数字
     * @param nums
     * @return
     */
    public static int singleNumber1(int[] nums) {
        int ret=0;
        for(int i=0;i<nums.length;i++){
            ret^=nums[i];
        }
        return ret;

    }
    public static int singleNumber(int[] nums) {
        Set<Integer> set=new TreeSet<>();//换成HashSet会更快
        for(int i=0;i<nums.length;i++){
           if(set.contains(nums[i])){
               set.remove(nums[i]);
           }else {
               set.add(nums[i]);
           }
        }
        for(int i=0;i<nums.length;i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     *复制带随机指针的链表
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur=head;
        while(cur!=null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }

    /**
     * 宝石与石头
     * 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
     * stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
     * 字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            char ch = jewels.charAt(i);
            set.add(ch);//把宝石放到集合里
        }
        int count=0;
        for(int i=0;i<stones.length();i++){
            char ch = stones.charAt(i);
            if(set.contains(ch)){
                count++;

            }
        }
        return count;

    }

    /**
     * 旧键盘
     * 输入：输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
     * 以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
     * 输出:按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。
     * @param str1
     * @param str2
     */
    public static void func(String str1,String str2){
        Set <Character> set = new HashSet<>();
        str2=str2.toUpperCase();
        for(int i=0;i<str2.length();i++){
            set.add(str2.charAt(i));
        }
        str1=str1.toUpperCase();
        Set <Character> set1 = new HashSet<>();

        for(int i=0;i<str1.length();i++){
            char ch = str1.charAt(i);
            if(!set.contains(ch)&&!set1.contains(ch)){
                set1.add(ch);
                System.out.print(ch+"");
            }
        }
    }

    /**
     * 前k个高频单词
     * @param words
     * @param k
     * @return
     */
    public static List<String> topKFrequent(String[] words, int k) {
        //1.统计单词出现的次数
        Map<String,Integer> map=new HashMap<>();//也可以用TreeMap但是效率没有hash高
        for (String word:words) {
            if(map.get(word)==null){
                map.put(word,1);
            }else {
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        //2.建立大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap= new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //比较频率
                if(o1.getValue().compareTo(o2.getValue())==0){
                    //做转换
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //遍历map
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size()<k){
                minHeap.offer(entry);

            }else {
                //此时需要与堆顶元素比较
                Map.Entry<String,Integer> top=  minHeap.peek();
                Integer val=top.getValue();
                if(val.compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);

                }else if(val.compareTo(entry.getValue())==0){
                    String key= top.getKey();
                    if(key.compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }

                }

            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            list.add(key);
        }
        Collections.reverse(list);
        return list;

    }

    /**
     * 字符串中的第一个唯一字符（HashMap版解法）
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i =0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.get(ch)==null){
                map.put(ch,1);
            }else{
                int val=map.get(ch);
                map.put(ch,val+1);
            }
        }
        for(int i =0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.get(ch)==1){
                return i;
            }

        }
        return -1;

    }

    public static void main(String[] args) {
        String[] w ={"i", "love", "leetcode", "i", "love", "coding"};
       List<String> list= topKFrequent(w,2);
        System.out.println(list);

    }
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String str1=in.nextLine();//期望
        String str2=in.nextLine();//实际
        func(str1,str2);


    }

    public static void main1(String[] args) {
        int[] nums={1,2,3,2,1};
        singleNumber(nums);

    }
}
